NSƯT Đỗ Minh Tuấn tham gia vào vai trò đạo diễn kiêm biên kịch của phim.[6] NSƯT Võ Hoài Nam là người được đạo diễn nhắm đến từ trước và đồng thời cũng đảm nhận vai diễn chính trong bộ phim.[7][8] Vai nữ chính ban đầu được giao cho một diễn viên múa, tuy nhiên Nguyễn Bích Ngọc sau đó đã thay thế vai trò này vì người trước đó đột ngột bỏ vai không thông báo.[9] Quá trình thực hiện phim mất bốn tháng để hoàn thành;[9] trong đó để tạo lập bối cảnh cho các cảnh quay của bộ phim, đoàn làm phim đã mất nửa năm để xây dựng một bãi rác trên bãi đất trống ven bờ sông Hồng, cũng như tìm gạch xây các căn nhà trên nền bãi phế liệu.[2]

Vua bãi rác được phát hành trong nước lần đầu vào tháng 10 năm 2002;[3] bộ phim cũng công chiếu tại nhiều liên hoan phim trong nước và quốc tế, trong đó có Liên hoan phim châu Á-Thái Bình Dương và Liên hoan phim quốc tế Palm Spring.[2][10][11] Tháng 7 năm 2003, phim đã được một hãng phim Canada mua bản quyền phát hành và công chiếu tại các rạp, truyền hình và DVD trong vòng 10 năm.[6][12] Phim cũng được mua bản quyền từ 8 nước khác nhau.[13] Năm 2007, bộ phim xuất hiện trong các suất chiếu của phòng chiếu phim IDECAF được tổ chức bởi Viện Trao đổi Văn hoá với Pháp.[14] Phim sau đó đã được phát sóng trong khung giờ "Phim cuối tuần" trên kênh truyền hình VTV1 vào năm 2014.[10][15]